{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Area Rectangle II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #geometry #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #几何 #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minAreaFreeRect"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小面积矩形 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定在 xy 平面上的一组点，确定由这些点组成的任何矩形的最小面积，其中矩形的边<strong>不一定平行于</strong> x 轴和 y 轴。</p>\n",
    "\n",
    "<p>如果没有任何矩形，就返回 0。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/22/1a.png\" style=\"height: 151px; width: 150px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>[[1,2],[2,1],[1,0],[0,1]]\n",
    "<strong>输出：</strong>2.00000\n",
    "<strong>解释：</strong>最小面积的矩形出现在 [1,2],[2,1],[1,0],[0,1] 处，面积为 2。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/23/2.png\" style=\"height: 94px; width: 150px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>[[0,1],[2,1],[1,1],[1,0],[2,0]]\n",
    "<strong>输出：</strong>1.00000\n",
    "<strong>解释：</strong>最小面积的矩形出现在 [1,0],[1,1],[2,1],[2,0] 处，面积为 1。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/23/3.png\" style=\"height: 94px; width: 150px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>[[0,3],[1,2],[3,1],[1,3],[2,1]]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>没法从这些点中组成任何矩形。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/21/4c.png\" style=\"height: 155px; width: 160px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>[[3,1],[1,1],[0,1],[2,1],[3,3],[3,2],[0,2],[2,3]]\n",
    "<strong>输出：</strong>2.00000\n",
    "<strong>解释：</strong>最小面积的矩形出现在 [2,1],[2,3],[3,3],[3,1] 处，面积为 2。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>1 &lt;= points.length &lt;= 50</code></li>\n",
    "\t<li><code>0 &lt;=&nbsp;points[i][0] &lt;=&nbsp;40000</code></li>\n",
    "\t<li><code>0 &lt;=&nbsp;points[i][1] &lt;=&nbsp;40000</code></li>\n",
    "\t<li>所有的点都是不同的。</li>\n",
    "\t<li>与真实值误差不超过 <code>10^-5</code>&nbsp;的答案将视为正确结果。</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-area-rectangle-ii](https://leetcode.cn/problems/minimum-area-rectangle-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-area-rectangle-ii](https://leetcode.cn/problems/minimum-area-rectangle-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2],[2,1],[1,0],[0,1]]', '[[0,1],[2,1],[1,1],[1,0],[2,0]]', '[[0,3],[1,2],[3,1],[1,3],[2,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaFreeRect(self, points: List[List[int]]) -> float:\n",
    "        EPS = 1e-7\n",
    "        points = set(map(tuple, points))\n",
    "        ans = inf\n",
    "        for p1, p2, p3 in itertools.permutations(points, 3):\n",
    "            p4 = p2[0] + p3[0] - p1[0], p2[1] + p3[1] - p1[1]\n",
    "            if p4 in points: # 平行四边形\n",
    "                v21 = (p2[0] - p1[0], p2[1] - p1[1])\n",
    "                v31 = (p3[0] - p1[0], p3[1] - p1[1])\n",
    "                if abs(v21[0] * v31[0] + v21[1] * v31[1]) < EPS: # 垂直\n",
    "                    area = (v21[0]*v21[0]+v21[1]*v21[1])**0.5 * (v31[0]*v31[0]+v31[1]*v31[1])**0.5\n",
    "                    if area < ans: # 最小面积\n",
    "                        ans = area\n",
    "\n",
    "        return ans if ans < inf else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaFreeRect(self, points: List[List[int]]) -> float:\n",
    "        hashpoints=set(map(tuple,points))\n",
    "        ans=float('inf')\n",
    "        for p1,p2,p3 in itertools.permutations(points,3):\n",
    "            p4=(p2[0]+p3[0]-p1[0],p2[1]+p3[1]-p1[1])\n",
    "            if p4 in hashpoints:\n",
    "                d12=complex(p2[0]-p1[0],p2[1]-p1[1])\n",
    "                d13=complex(p3[0]-p1[0],p3[1]-p1[1])\n",
    "                if abs(d12.real*d13.real+d12.imag*d13.imag)==0:\n",
    "                    area=abs(d12)*abs(d13)\n",
    "                    ans=min(area,ans)\n",
    "        return ans if ans<float('inf') else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaFreeRect(self, points: List[List[int]]) -> float:\n",
    "        s, res = {tuple(x) for x in points}, inf\n",
    "        for i in range(len(points)):\n",
    "            for j in range(len(points) - 1):\n",
    "                if j != i:\n",
    "                    for k in range(j + 1, len(points)):\n",
    "                        if k != i and (points[i][0] - points[j][0]) * (points[i][0] - points[k][0]) + (points[i][1] - points[j][1]) * (points[i][1] - points[k][1]) == 0 and (points[j][0] + points[k][0] - points[i][0], points[j][1] + points[k][1] - points[i][1]) in s:\n",
    "                            res = min(res, sqrt(((points[i][0] - points[j][0]) ** 2 + (points[i][1] - points[j][1]) ** 2) * ((points[i][0] - points[k][0]) ** 2 + (points[i][1] - points[k][1]) ** 2)))\n",
    "        return res if res != inf else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minAreaFreeRect(self, points):\n",
    "        EPS = 1e-7\n",
    "        points = set(map(tuple, points))\n",
    "\n",
    "        ans = float('inf')\n",
    "        for p1, p2, p3 in permutations(points, 3):\n",
    "            p4 = p2[0] + p3[0] - p1[0], p2[1] + p3[1] - p1[1]\n",
    "            if p4 in points:\n",
    "                v21 = complex(p2[0] - p1[0], p2[1] - p1[1])\n",
    "                v31 = complex(p3[0] - p1[0], p3[1] - p1[1])\n",
    "                if abs(v21.real * v31.real + v21.imag * v31.imag) < EPS:\n",
    "                    area = abs(v21) * abs(v31)\n",
    "                    ans = min(ans, area)\n",
    "\n",
    "        return ans if ans < float('inf') else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaFreeRect(self, points: List[List[int]]) -> float:\n",
    "        EPS = 1e-7\n",
    "        points = set(map(tuple, points))\n",
    "        ans = float('inf')\n",
    "        for p1, p2, p3 in itertools.permutations(points, 3):\n",
    "            p4 = p2[0] + p3[0] - p1[0], p2[1] + p3[1] - p1[1]\n",
    "            if p4 in points:\n",
    "                v21 = complex(p2[0] - p1[0], p2[1] - p1[1]) \n",
    "                v31 = complex(p3[0] - p1[0], p3[1] - p1[1]) \n",
    "                if abs(v21.real * v31.real + v21.imag * v31.imag) < EPS:\n",
    "                    area = abs(v21) * abs(v31)\n",
    "                    if area < ans:\n",
    "                        ans = area\n",
    "        return ans if ans < float('inf') else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaFreeRect(self, points: List[List[int]]) -> float:\n",
    "        points = set(map(tuple, points))\n",
    "        ff = itertools.permutations(points, 3)\n",
    "        ans = float('inf')\n",
    "        for p1, p2, p3 in ff:\n",
    "            x, y = p1[0] + p2[0] - p3[0], p1[1] + p2[1] - p3[1]\n",
    "            if (x, y) in points:\n",
    "                if (p3[0] - p1[0]) * (p2[0] - p3[0]) + (p3[1] - p1[1]) * (p2[1] - p3[1]) == 0:\n",
    "                    aero = (((p3[0] - p1[0]) ** 2 + (p3[1] - p1[1]) ** 2) * (\n",
    "                                (p2[0] - p3[0]) ** 2 + (p2[1] - p3[1]) ** 2)) ** 0.5\n",
    "                    ans = min(ans, aero)\n",
    "        return 0 if ans == float('inf') else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaFreeRect(self, points: List[List[int]]) -> float:\n",
    "        EPS = 1e-7\n",
    "        points = set(map(tuple, points))\n",
    "        \n",
    "        ans = float('inf')\n",
    "        \n",
    "        for p1, p2, p3 in itertools.permutations(points, 3):\n",
    "            p4x = p2[0] - p1[0] + p3[0] - p1[0] + p1[0]\n",
    "            p4y = p2[1] - p1[1] + p3[1] - p1[1] + p1[1]\n",
    "            \n",
    "            if (p4x, p4y) in points:\n",
    "                #inner product 90degree\n",
    "                if (p2[0] - p1[0]) * (p3[0]- p1[0]) + (p2[1] - p1[1]) * (p3[1]- p1[1]) ==0: \n",
    "                    # 叉积\n",
    "                    area = abs((p2[0] - p1[0]) * (p3[1]- p1[1]) - (p2[1] - p1[1]) * (p3[0]- p1[0]))\n",
    "                    if area < ans:\n",
    "                        ans = area\n",
    "                        \n",
    "        return ans if ans < float('inf') else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minAreaFreeRect(self, points):\n",
    "        EPS = 1e-7\n",
    "        points = set(map(tuple, points))\n",
    "\n",
    "        ans = float('inf')\n",
    "        for p1, p2, p3 in itertools.permutations(points, 3):\n",
    "            p4 = p2[0] + p3[0] - p1[0], p2[1] + p3[1] - p1[1]\n",
    "            if p4 in points:\n",
    "                v21 = complex(p2[0] - p1[0], p2[1] - p1[1])\n",
    "                v31 = complex(p3[0] - p1[0], p3[1] - p1[1])\n",
    "                if abs(v21.real * v31.real + v21.imag * v31.imag) < EPS:\n",
    "                    area = abs(v21) * abs(v31)\n",
    "                    if area < ans:\n",
    "                        ans = area\n",
    "\n",
    "        return ans if ans < float('inf') else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaFreeRect(self, points: List[List[int]]) -> float:\n",
    "        EPS = 1e-7\n",
    "        points = set(map(tuple, points))\n",
    "\n",
    "        ans = float('inf')\n",
    "        for p1, p2, p3 in itertools.permutations(points, 3):\n",
    "            p4 = p2[0] + p3[0] - p1[0], p2[1] + p3[1] - p1[1]\n",
    "            if p4 in points:\n",
    "                v21 = complex(p2[0] - p1[0], p2[1] - p1[1])\n",
    "                v22 = complex(p3[0] - p1[0], p3[1] - p1[1])\n",
    "                if abs(v21.real * v22.real + v21.imag * v22.imag) < EPS:\n",
    "                    area = abs(v21) * abs(v22)\n",
    "                    if area < ans:\n",
    "                        ans = area\n",
    "        \n",
    "        return ans if ans < float('inf') else 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaFreeRect(self, points: List[List[int]]) -> float:\n",
    "        n = len(points)\n",
    "        \n",
    "        points_set = set(map(tuple, points))    #加速查找 hash，空间换取时间\n",
    "\n",
    "        ######## 所有的点都不同，每次取3个点，计算第4个点“应该”在哪里，“探”一下存不存在\n",
    "        res = float('inf')\n",
    "        for i in range(n):\n",
    "            [x1, y1] = points[i]\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                [x2,y2] = points[j]\n",
    "                for k in range(j + 1, n):\n",
    "                    if k == i:\n",
    "                        continue\n",
    "                    [x3, y3] = points[k]\n",
    "                    #### p2 p3为副对角线，p1为一个顶角\n",
    "                    x4 = x2 + x3 - x1\n",
    "                    y4 = y2 + y3 - y1\n",
    "                    if (x4, y4) in points_set:          #“探”一下，第4个点，是否存在\n",
    "                        v21 = (x2 - x1,  y2 - y1)\n",
    "                        v31 = (x3 - x1,  y3 - y1)\n",
    "                        if v21[0] * v31[0] + v21[1] * v31[1] == 0:  #判断垂直。2个向量的内积为0\n",
    "                            cur_area = (v21[0] ** 2 + v21[1] ** 2)**0.5 * (v31[0] ** 2 + v31[1] ** 2)**0.5\n",
    "                            if cur_area < res:\n",
    "                                res = cur_area\n",
    "        return res if res != float('inf') else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaFreeRect(self, points: List[List[int]]) -> float:\n",
    "        points_set = set(map(tuple, points))\n",
    "        res = float('inf')\n",
    "        for p1, p2, p3 in itertools.permutations(points, 3):\n",
    "            p4 = p2[0] + p3[0] - p1[0], p2[1] + p3[1] - p1[1]\n",
    "            if p4 in points_set:\n",
    "                v21 = complex(p2[0] - p1[0], p2[1] - p1[1])\n",
    "                v31 = complex(p3[0] - p1[0], p3[1] - p1[1])\n",
    "                if abs(v21.real * v31.real + v21.imag * v31.imag) == 0: # 判断是否垂直\n",
    "                    area = abs(v21) * abs(v31) # abs(complex(1,1)) = 1.414\n",
    "                    if area < res:\n",
    "                        res = area\n",
    "        return res if res != float('inf') else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaFreeRect(self, points: List[List[int]]) -> float:\n",
    "        s = set(map(tuple, points))\n",
    "        def check(points):\n",
    "            perm = permutations(points)\n",
    "            for p in perm:\n",
    "                (x1, y1), (x2, y2), (x3, y3) = p[0], p[1], p[2]\n",
    "                v1, v2 = [x2 - x1, y2 - y1], [x3 - x2, y3 - y2]\n",
    "                x4, y4 = x1 + x3 - x2, y1 + y3 - y2\n",
    "                if v1[0] * v2[0] + v1[1] * v2[1] == 0 and (x4, y4) in s:\n",
    "                    a = sqrt(v1[0] ** 2 + v1[1] ** 2)\n",
    "                    b = sqrt(v2[0] ** 2 + v2[1] ** 2)\n",
    "                    return a * b\n",
    "            return False\n",
    "            \n",
    "        n, res = len(points), inf\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                for k in range(j + 1, n):\n",
    "                    three = [points[i], points[j], points[k]]\n",
    "                    if check(three):\n",
    "                        res = min(res, check(three))\n",
    "        return res if res != inf else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "class Solution:\n",
    "    def minAreaFreeRect(self, points: List[List[int]]) -> float:\n",
    "        result = float('inf')\n",
    "        \n",
    "        for x, y, z in itertools.permutations(points, 3):\n",
    "            z2x = [x[0] - z[0], x[1] - z[1]]\n",
    "            z2y = [y[0] - z[0], y[1] - z[1]]\n",
    "            if z2x[0] * z2y[0] + z2x[1] * z2y[1] != 0:\n",
    "                continue\n",
    "            target = [x[0] + y[0] - z[0], x[1] + y[1] - z[1]]\n",
    "            if target in points:\n",
    "                a = ((x[0] - z[0])**2 + (x[1] - z[1])**2)**0.5\n",
    "                b = ((y[0] - z[0])**2 + (y[1] - z[1])**2)**0.5\n",
    "                area = a * b\n",
    "                result = min(area, result)\n",
    "        \n",
    "        return result if result != float('inf') else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\r\n",
    "# @lc app=leetcode.cn id=963 lang=python3\r\n",
    "#\r\n",
    "# [963] 最小面积矩形 II\r\n",
    "#\r\n",
    "# https://leetcode.cn/problems/minimum-area-rectangle-ii/description/\r\n",
    "#\r\n",
    "# algorithms\r\n",
    "# Medium (51.22%)\r\n",
    "# Likes:    66\r\n",
    "# Dislikes: 0\r\n",
    "# Total Accepted:    3.9K\r\n",
    "# Total Submissions: 7.6K\r\n",
    "# Testcase Example:  '[[1,2],[2,1],[1,0],[0,1]]'\r\n",
    "#\r\n",
    "# 给定在 xy 平面上的一组点，确定由这些点组成的任何矩形的最小面积，其中矩形的边不一定平行于 x 轴和 y 轴。\r\n",
    "# \r\n",
    "# 如果没有任何矩形，就返回 0。\r\n",
    "# \r\n",
    "# \r\n",
    "# \r\n",
    "# 示例 1：\r\n",
    "# \r\n",
    "# \r\n",
    "# \r\n",
    "# 输入：[[1,2],[2,1],[1,0],[0,1]]\r\n",
    "# 输出：2.00000\r\n",
    "# 解释：最小面积的矩形出现在 [1,2],[2,1],[1,0],[0,1] 处，面积为 2。\r\n",
    "# \r\n",
    "# 示例 2：\r\n",
    "# \r\n",
    "# \r\n",
    "# \r\n",
    "# 输入：[[0,1],[2,1],[1,1],[1,0],[2,0]]\r\n",
    "# 输出：1.00000\r\n",
    "# 解释：最小面积的矩形出现在 [1,0],[1,1],[2,1],[2,0] 处，面积为 1。\r\n",
    "# \r\n",
    "# \r\n",
    "# 示例 3：\r\n",
    "# \r\n",
    "# \r\n",
    "# \r\n",
    "# 输入：[[0,3],[1,2],[3,1],[1,3],[2,1]]\r\n",
    "# 输出：0\r\n",
    "# 解释：没法从这些点中组成任何矩形。\r\n",
    "# \r\n",
    "# \r\n",
    "# 示例 4：\r\n",
    "# \r\n",
    "# \r\n",
    "# \r\n",
    "# 输入：[[3,1],[1,1],[0,1],[2,1],[3,3],[3,2],[0,2],[2,3]]\r\n",
    "# 输出：2.00000\r\n",
    "# 解释：最小面积的矩形出现在 [2,1],[2,3],[3,3],[3,1] 处，面积为 2。\r\n",
    "# \r\n",
    "# \r\n",
    "# \r\n",
    "# \r\n",
    "# 提示：\r\n",
    "# \r\n",
    "# \r\n",
    "# 1 <= points.length <= 50\r\n",
    "# 0 <= points[i][0] <= 40000\r\n",
    "# 0 <= points[i][1] <= 40000\r\n",
    "# 所有的点都是不同的。\r\n",
    "# 与真实值误差不超过 10^-5 的答案将视为正确结果。\r\n",
    "# \r\n",
    "# \r\n",
    "#\r\n",
    "\r\n",
    "# @lc code=start\r\n",
    "class Solution:\r\n",
    "    def isRectangle(self, p1, p2, p3, p4):\r\n",
    "        # 判断是否为直角\r\n",
    "        if (p2[0]-p1[0])*(p3[0]-p1[0])+(p2[1]-p1[1])*(p3[1]-p1[1])==0:\r\n",
    "            return True\r\n",
    "        return False\r\n",
    "    def calcArea(self, p1, p2, p3):\r\n",
    "        # 计算面积\r\n",
    "        return ( (p2[0]-p1[0])**2 + (p2[1]-p1[1])**2 )**0.5 * ( (p3[0]-p1[0])**2 + (p3[1]-p1[1])**2 )**0.5\r\n",
    "    def minAreaFreeRect(self, points: List[List[int]]) -> float:\r\n",
    "        points = set(map(tuple, points))\r\n",
    "        res = float('inf')\r\n",
    "        for p1,p2,p3 in itertools.permutations(points, 3):\r\n",
    "            # 求出p4\r\n",
    "            p4 = (p2[0]+p3[0]-p1[0], p2[1]+p3[1]-p1[1])\r\n",
    "            # 判断p4是否在points中\r\n",
    "            if p4 in points:\r\n",
    "                # 判断是否为直角\r\n",
    "                if self.isRectangle(p1, p2, p3, p4):\r\n",
    "                    res = min(res, self.calcArea(p1, p2, p3))\r\n",
    "        return res if res!=float('inf') else 0\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaFreeRect(self, points: List[List[int]]) -> float:\n",
    "        points = {tuple(a) for a in points}\n",
    "\n",
    "        ans = inf\n",
    "        for (x1, y1), (x2, y2), (x3, y3) in permutations(points, 3):\n",
    "            x, y = x2 + x3 - x1, y2 + y3 - y1\n",
    "            if (x, y) in points and (x2 - x1) * (x3 - x1) + (y2 - y1) * (y3 - y1) == 0:\n",
    "                ans = min(ans, ((x2 - x1) ** 2 + (y2 - y1) ** 2) * ((x3 - x1) ** 2 + (y3 - y1) ** 2))\n",
    "        return 0 if ans == inf else ans ** 0.5 \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaFreeRect(self, points: List[List[int]]) -> float:\n",
    "        s = set(tuple(p) for p in points)\n",
    "        def check(points):\n",
    "            perm = permutations(points)\n",
    "            for p in perm:\n",
    "                (x1, y1), (x2, y2), (x3, y3) = p[0], p[1], p[2]\n",
    "                v1, v2 = [x2 - x1, y2 - y1], [x3 - x2, y3 - y2]\n",
    "                x4, y4 = x1 + x3 - x2, y1 + y3 - y2\n",
    "                if v1[0] * v2[0] + v1[1] * v2[1] == 0 and (x4, y4) in s:\n",
    "                    a = sqrt(v1[0] ** 2 + v1[1] ** 2)\n",
    "                    b = sqrt(v2[0] ** 2 + v2[1] ** 2)\n",
    "                    return a * b\n",
    "            return False\n",
    "            \n",
    "        n, res = len(points), inf\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                for k in range(j + 1, n):\n",
    "                    three = [points[i], points[j], points[k]]\n",
    "                    if check(three):\n",
    "                        res = min(res, check(three))\n",
    "        return res if res != inf else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaFreeRect(self, points: List[List[int]]) -> float:\n",
    "        diff = 1e-7\n",
    "        points = set(map(tuple, points))\n",
    "\n",
    "        res = float('inf')\n",
    "        for p1, p2, p3 in itertools.permutations(points, 3):\n",
    "            p4 = (p2[0] + p3[0] - p1[0], p2[1] + p3[1] - p1[1])\n",
    "            if p4 in points:\n",
    "                # vertice multiple = 0\n",
    "                v21 = complex(p2[0] - p1[0], p2[1] - p1[1])\n",
    "                v31 = complex(p3[0] - p1[0], p3[1] - p1[1])\n",
    "                if abs(v21.real * v31.real + v21.imag * v31.imag) < diff:\n",
    "                    area = abs(v21) * abs(v31)\n",
    "                    if area < res:\n",
    "                        res = area\n",
    "        return res if res < float('inf') else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaFreeRect(self, points: List[List[int]]) -> float:\n",
    "        s = set(tuple(p) for p in points)\n",
    "        def getArea(x1, y1, x2, y2, x3, y3):\n",
    "            a = sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)\n",
    "            b = sqrt((x2 - x3) ** 2 + (y2 - y3) ** 2)\n",
    "            return a * b\n",
    "        def check(points):\n",
    "            perm = permutations(points)\n",
    "            for p in perm:\n",
    "                (x1, y1), (x2, y2), (x3, y3) = p[0], p[1], p[2]\n",
    "                v1, v2 = [x2 - x1, y2 - y1], [x3 - x2, y3 - y2]\n",
    "                x4, y4 = x1 + x3 - x2, y1 + y3 - y2\n",
    "                if v1[0] * v2[0] + v1[1] * v2[1] == 0 and (x4, y4) in s:\n",
    "                    return getArea(x1, y1, x2, y2, x3, y3)\n",
    "            return False\n",
    "            \n",
    "        n, res = len(points), inf\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                for k in range(j + 1, n):\n",
    "                    three = [points[i], points[j], points[k]]\n",
    "                    if check(three):\n",
    "                        res = min(res, check(three))\n",
    "        return res if res != inf else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "class Solution:\n",
    "    def minAreaFreeRect(self, points: List[List[int]]) -> float:\n",
    "        result = float('inf')\n",
    "        points = set(map(tuple, points))\n",
    "        \n",
    "        for x, y, z in itertools.permutations(points, 3):\n",
    "            z2x = (x[0] - z[0], x[1] - z[1])\n",
    "            z2y = (y[0] - z[0], y[1] - z[1])\n",
    "            if z2x[0] * z2y[0] + z2x[1] * z2y[1] != 0:\n",
    "                continue\n",
    "            target = (x[0] + y[0] - z[0], x[1] + y[1] - z[1])\n",
    "            if target in points:\n",
    "                a = ((x[0] - z[0])**2 + (x[1] - z[1])**2)**0.5\n",
    "                b = ((y[0] - z[0])**2 + (y[1] - z[1])**2)**0.5\n",
    "                area = a * b\n",
    "                result = min(area, result)\n",
    "        \n",
    "        return result if result != float('inf') else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minAreaFreeRect(self, points):\n",
    "        EPS = 1e-7\n",
    "        points = set(map(tuple, points))\n",
    "\n",
    "        ans = float('inf')\n",
    "        for p1, p2, p3 in itertools.permutations(points, 3):\n",
    "            p4 = p2[0] + p3[0] - p1[0], p2[1] + p3[1] - p1[1]\n",
    "            if p4 in points:\n",
    "                v21 = complex(p2[0] - p1[0], p2[1] - p1[1])\n",
    "                v31 = complex(p3[0] - p1[0], p3[1] - p1[1])\n",
    "                if abs(v21.real * v31.real + v21.imag * v31.imag) < EPS:\n",
    "                    area = abs(v21) * abs(v31)\n",
    "                    if area < ans:\n",
    "                        ans = area\n",
    "\n",
    "        return ans if ans < float('inf') else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaFreeRect(self, points: List[List[int]]) -> float:\n",
    "        n = len(points)\n",
    "        \n",
    "        points_set = set(map(tuple, points))    #加速查找 hash，空间换取时间\n",
    "\n",
    "        ######## 所有的点都不同，每次取3个点，计算第4个点“应该”在哪里，“探”一下存不存在\n",
    "        res = float('inf')\n",
    "        for i in range(n):\n",
    "            [x1, y1] = points[i]\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                [x2,y2] = points[j]\n",
    "                for k in range(j + 1, n):\n",
    "                    if k == i:\n",
    "                        continue\n",
    "                    [x3, y3] = points[k]\n",
    "                    #### p2 p3为副对角线，p1为一个顶角\n",
    "                    x4 = x2 + x3 - x1\n",
    "                    y4 = y2 + y3 - y1\n",
    "                    if (x4, y4) in points_set:          #“探”一下，第4个点，是否存在\n",
    "                        v21 = (x2 - x1,  y2 - y1)\n",
    "                        v31 = (x3 - x1,  y3 - y1)\n",
    "                        if v21[0] * v31[0] + v21[1] * v31[1] == 0:  #判断垂直。2个向量的内积为0\n",
    "                            cur_area = (v21[0] ** 2 + v21[1] ** 2)**0.5 * (v31[0] ** 2 + v31[1] ** 2)**0.5\n",
    "                            if cur_area < res:\n",
    "                                res = cur_area\n",
    "        return res if res != float('inf') else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaFreeRect(self, points: List[List[int]]) -> float:\n",
    "        EPS = 1e-7\n",
    "        points = set(map(tuple, points))\n",
    "\n",
    "        min_area = float('inf')\n",
    "\n",
    "        for p1, p2, p3 in itertools.permutations(points, 3):\n",
    "            p4 = p2[0] + p3[0] - p1[0], p2[1] + p3[1] - p1[1]\n",
    "            if p4 in points:\n",
    "                v21 = complex(p2[0] - p1[0], p2[1] - p1[1])\n",
    "                v31 = complex(p3[0] - p1[0], p3[1] - p1[1])\n",
    "                if abs(v21.real * v31.real + v21.imag * v31.imag) < EPS:\n",
    "                    area = abs(v21) * abs(v31)\n",
    "                    min_area = min(min_area, area)\n",
    "        return min_area if min_area != float('inf') else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def minAreaFreeRect(self, points: List[List[int]]) -> float:\n",
    "        pointSet = set(map(tuple, points))\n",
    "        ans = float('inf')\n",
    "        \n",
    "        for i in range(len(points)):\n",
    "            p1 = points[i]\n",
    "            for j in range(len(points)):\n",
    "                if j == i:\n",
    "                    continue\n",
    "                p2 = points[j]\n",
    "                \n",
    "                for k in range(len(points)):\n",
    "                    if k == i or k == j:\n",
    "                        continue\n",
    "                    p3 = points[k]\n",
    "                    \n",
    "                    # 由p1、p2、p3确定p4\n",
    "                    p4 = (p2[0] + p3[0] - p1[0], p2[1] + p3[1] - p1[1])\n",
    "                    \n",
    "                    if p4 in pointSet:\n",
    "                        vec21 = [p2[0]-p1[0], p2[1]-p1[1]]\n",
    "                        vec31 = [p3[0]-p1[0], p3[1]-p1[1]]\n",
    "                        \n",
    "                        # 检查p2、p3是否为垂直\n",
    "                        if vec21[0]*vec31[0] + vec21[1]*vec31[1] == 0:\n",
    "                            area = math.sqrt(vec21[0]**2 + vec21[1]**2) * \\\n",
    "                                   math.sqrt(vec31[0]**2 + vec31[1]**2)\n",
    "                            ans = min(ans, area)\n",
    "        return 0 if ans == float('inf') else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minAreaFreeRect(self, points):\n",
    "        EPS = 1e-7\n",
    "        points = set(map(tuple, points))\n",
    "\n",
    "        ans = float('inf')\n",
    "        for p1, p2, p3 in itertools.permutations(points, 3):\n",
    "            p4 = p2[0] + p3[0] - p1[0], p2[1] + p3[1] - p1[1]\n",
    "            if p4 in points:\n",
    "                v21 = complex(p2[0] - p1[0], p2[1] - p1[1])\n",
    "                v31 = complex(p3[0] - p1[0], p3[1] - p1[1])\n",
    "                if abs(v21.real * v31.real + v21.imag * v31.imag) < EPS:\n",
    "                    area = abs(v21) * abs(v31)\n",
    "                    if area < ans:\n",
    "                        ans = area\n",
    "\n",
    "        return ans if ans < float('inf') else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaFreeRect(self, points: List[List[int]]) -> float:\n",
    "        pointset = set()\n",
    "        for i, j in points:\n",
    "            pointset.add((i, j))\n",
    "        res = float('inf')\n",
    "        for i in range(len(points)):\n",
    "            for j in range(len(points)):\n",
    "                if i != j:\n",
    "                    for k in range(j + 1, len(points)):\n",
    "                        if k != i:\n",
    "                            x1, y1 = points[i]\n",
    "                            x2, y2 = points[j]\n",
    "                            x3, y3 = points[k]\n",
    "                            x4 = x2 + x3 - x1\n",
    "                            y4 = y2 + y3 - y1\n",
    "                            if (x4, y4) in pointset:\n",
    "                                v21 = (x2 - x1,  y2 - y1)\n",
    "                                v31 = (x3 - x1,  y3 - y1)\n",
    "                                if v21[0] * v31[0] + v21[1] * v31[1] == 0:\n",
    "                                    cur_area = (v21[0] ** 2 + v21[1] ** 2)**0.5 * (v31[0] ** 2 + v31[1] ** 2)**0.5\n",
    "                                    if cur_area < res:\n",
    "                                        res = cur_area\n",
    "        return res if res != float('inf') else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minAreaFreeRect(self, p: List[List[int]]) -> float:\r\n",
    "        n = len(p)\r\n",
    "        res = inf\r\n",
    "\r\n",
    "        ps = {(x, y): i for i, (x, y) in enumerate(p)}\r\n",
    "        # 向量 平行 \r\n",
    "        def check(A, B):\r\n",
    "            return A[0] * B[1] - A[1] * B[0] == 0\r\n",
    "        \r\n",
    "        # 向量 垂直 \r\n",
    "        def check2(A, B):\r\n",
    "            return A[0] * B[0] + A[1] * B[1] == 0\r\n",
    "\r\n",
    "        # 交差积\r\n",
    "        def cross(A, B):\r\n",
    "            return A[0] * B[1] - A[1] * B[0]\r\n",
    "        \r\n",
    "        # 计算向量 \r\n",
    "        def vec(a, b):\r\n",
    "            return (b[0] - a[0], b[1] - a[1])\r\n",
    "        \r\n",
    "        @cache\r\n",
    "        def calc(i, j, k, m):\r\n",
    "            a, b, c, d = p[i], p[j], p[k], p[m]\r\n",
    "            if check(vec(a, d), vec(b, c)) and check(vec(a, b), vec(d, c)) and check2(vec(a, b), vec(a, d)) and check2(vec(b, a), vec(b, c)):\r\n",
    "                return abs(cross(vec(a, b),vec(a, d)))\r\n",
    "            return inf \r\n",
    "\r\n",
    "        for i in range(n):\r\n",
    "            for j in range(n):\r\n",
    "                if j == i:continue\r\n",
    "                for k in range(n):\r\n",
    "                    if k == i or k == j:continue\r\n",
    "                    v = vec(p[j], p[k])\r\n",
    "                    x, y = p[i][0] + v[0], p[i][1] + v[1]\r\n",
    "                    if (x, y) not in ps:\r\n",
    "                        continue\r\n",
    "                    res = min(res, calc(i, j, k, ps[x, y]))\r\n",
    "        return res if res != inf else 0\r\n",
    "\r\n",
    "\r\n",
    "                        \r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\r\n",
    "# @lc app=leetcode.cn id=963 lang=python3\r\n",
    "#\r\n",
    "# [963] 最小面积矩形 II\r\n",
    "#\r\n",
    "# https://leetcode.cn/problems/minimum-area-rectangle-ii/description/\r\n",
    "#\r\n",
    "# algorithms\r\n",
    "# Medium (51.22%)\r\n",
    "# Likes:    66\r\n",
    "# Dislikes: 0\r\n",
    "# Total Accepted:    3.9K\r\n",
    "# Total Submissions: 7.6K\r\n",
    "# Testcase Example:  '[[1,2],[2,1],[1,0],[0,1]]'\r\n",
    "#\r\n",
    "# 给定在 xy 平面上的一组点，确定由这些点组成的任何矩形的最小面积，其中矩形的边不一定平行于 x 轴和 y 轴。\r\n",
    "# \r\n",
    "# 如果没有任何矩形，就返回 0。\r\n",
    "# \r\n",
    "# \r\n",
    "# \r\n",
    "# 示例 1：\r\n",
    "# \r\n",
    "# \r\n",
    "# \r\n",
    "# 输入：[[1,2],[2,1],[1,0],[0,1]]\r\n",
    "# 输出：2.00000\r\n",
    "# 解释：最小面积的矩形出现在 [1,2],[2,1],[1,0],[0,1] 处，面积为 2。\r\n",
    "# \r\n",
    "# 示例 2：\r\n",
    "# \r\n",
    "# \r\n",
    "# \r\n",
    "# 输入：[[0,1],[2,1],[1,1],[1,0],[2,0]]\r\n",
    "# 输出：1.00000\r\n",
    "# 解释：最小面积的矩形出现在 [1,0],[1,1],[2,1],[2,0] 处，面积为 1。\r\n",
    "# \r\n",
    "# \r\n",
    "# 示例 3：\r\n",
    "# \r\n",
    "# \r\n",
    "# \r\n",
    "# 输入：[[0,3],[1,2],[3,1],[1,3],[2,1]]\r\n",
    "# 输出：0\r\n",
    "# 解释：没法从这些点中组成任何矩形。\r\n",
    "# \r\n",
    "# \r\n",
    "# 示例 4：\r\n",
    "# \r\n",
    "# \r\n",
    "# \r\n",
    "# 输入：[[3,1],[1,1],[0,1],[2,1],[3,3],[3,2],[0,2],[2,3]]\r\n",
    "# 输出：2.00000\r\n",
    "# 解释：最小面积的矩形出现在 [2,1],[2,3],[3,3],[3,1] 处，面积为 2。\r\n",
    "# \r\n",
    "# \r\n",
    "# \r\n",
    "# \r\n",
    "# 提示：\r\n",
    "# \r\n",
    "# \r\n",
    "# 1 <= points.length <= 50\r\n",
    "# 0 <= points[i][0] <= 40000\r\n",
    "# 0 <= points[i][1] <= 40000\r\n",
    "# 所有的点都是不同的。\r\n",
    "# 与真实值误差不超过 10^-5 的答案将视为正确结果。\r\n",
    "# \r\n",
    "# \r\n",
    "#\r\n",
    "\r\n",
    "# @lc code=start\r\n",
    "class Solution:\r\n",
    "    def isRectangle(self, p1, p2, p3):\r\n",
    "        # 判断是否为直角\r\n",
    "        if (p2[0]-p1[0])*(p3[0]-p1[0])+(p2[1]-p1[1])*(p3[1]-p1[1])==0:\r\n",
    "            return True\r\n",
    "        return False\r\n",
    "    def calcArea(self, p1, p2, p3):\r\n",
    "        # 计算面积\r\n",
    "        return ( (p2[0]-p1[0])**2 + (p2[1]-p1[1])**2 )**0.5 * ( (p3[0]-p1[0])**2 + (p3[1]-p1[1])**2 )**0.5\r\n",
    "    def minAreaFreeRect(self, points: List[List[int]]) -> float:\r\n",
    "        points = set(map(tuple, points))\r\n",
    "        res = float('inf')\r\n",
    "        for p1,p2,p3 in itertools.permutations(points, 3):\r\n",
    "            # 求出p4\r\n",
    "            p4 = (p2[0]+p3[0]-p1[0], p2[1]+p3[1]-p1[1])\r\n",
    "            # 判断p4是否在points中\r\n",
    "            if p4 in points:\r\n",
    "                # 判断是否为直角\r\n",
    "                if self.isRectangle(p1, p2, p3):\r\n",
    "                    res = min(res, self.calcArea(p1, p2, p3))\r\n",
    "        return res if res!=float('inf') else 0\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "class Solution:\n",
    "    def minAreaFreeRect(self, points: List[List[int]]) -> float:\n",
    "        result = float('inf')\n",
    "        points = set(map(tuple, points))\n",
    "        \n",
    "        for x, y, z in itertools.permutations(points, 3):\n",
    "            z2x = (x[0] - z[0], x[1] - z[1])\n",
    "            z2y = (y[0] - z[0], y[1] - z[1])\n",
    "            if z2x[0] * z2y[0] + z2x[1] * z2y[1] != 0:\n",
    "                continue\n",
    "            target = (x[0] + y[0] - z[0], x[1] + y[1] - z[1])\n",
    "            if target in points:\n",
    "                a = ((x[0] - z[0])**2 + (x[1] - z[1])**2)**0.5\n",
    "                b = ((y[0] - z[0])**2 + (y[1] - z[1])**2)**0.5\n",
    "                area = a * b\n",
    "                result = min(area, result)\n",
    "        \n",
    "        return result if result != float('inf') else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaFreeRect(self, points: List[List[int]]) -> float:\n",
    "        # 给你50个点，然后50个点都是不相同的，然后让你找出这些点组成的最小矩形面积\n",
    "        # 给你4个点，然后让你判断这四个点是否能组成矩形？\n",
    "        points = [complex(*z) for z in points]\n",
    "        seen = defaultdict(list)\n",
    "        for P,Q in combinations(points,2):\n",
    "            # 中心点\n",
    "            center = (P+Q)/2\n",
    "            radius = abs(center-P)\n",
    "            seen[center,radius].append(P)\n",
    "        ans = float('inf')\n",
    "        for (center,radius),candidates in seen.items():\n",
    "            for P,Q in combinations(candidates,2):\n",
    "                ans = min(ans,abs(P-Q)*abs(P-(2*center - Q)))\n",
    "        return ans if ans < float('inf') else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaFreeRect(self, points: List[List[int]]) -> float:\n",
    "        n=len(points)\n",
    "        def dist(x1, y1, x2, y2):\n",
    "            return ((x1-x2)**2 + (y1-y2)**2)**.5\n",
    "        \n",
    "        def vector(x1, y1, x2, y2):\n",
    "            return (x1-x2, y1-y2)\n",
    "\n",
    "        def area(p1, p2, p3, p4):\n",
    "            x1, y1 = points[p1]\n",
    "            x_1, y_1 = points[p2]\n",
    "            x2, y2 = points[p3]\n",
    "            x_2, y_2 = points[p4]\n",
    "\n",
    "            line1 = vector(x1, y1, x2, y2)\n",
    "            line2 = vector(x1, y1, x_2, y_2)       \n",
    "\n",
    "            if line1[0]*line2[0] + line2[1]*line1[1]!=0:\n",
    "                return float('inf')\n",
    "            return dist(x1, y1, x2, y2) * dist(x1, y1, x_2, y_2)  \n",
    "        \n",
    "        centers = defaultdict(list)\n",
    "        for i in range(n-1):\n",
    "            x1, y1 = points[i]\n",
    "            for j in range(i+1, n):\n",
    "                x2, y2 = points[j]\n",
    "                centers[((x1 + x2)/2, (y1 + y2)/2)].append((i,j))\n",
    "        # print(centers)\n",
    "        ans = float('inf')\n",
    "        for k in centers:\n",
    "            n = len(centers[k])\n",
    "            for i in range(n-1):\n",
    "                l1, r1 = centers[k][i]\n",
    "                for j in range(i+1, n):\n",
    "                    # if l1 in centers[k][j] or r1 in centers[k][j]:continue\n",
    "                    l2, r2 = centers[k][j]\n",
    "                    ans = min(ans, area(l1, r1, l2, r2))\n",
    "        \n",
    "        return ans if ans < float('inf') else 0   \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaFreeRect(self, points: List[List[int]]) -> float:\n",
    "        n=len(points)\n",
    "        def dist(x1, y1, x2, y2):\n",
    "            return ((x1-x2)**2 + (y1-y2)**2)**.5\n",
    "        \n",
    "        def vector(x1, y1, x2, y2):\n",
    "            return (x1-x2, y1-y2)\n",
    "\n",
    "        def area(p1, p2, p3, p4):\n",
    "            x1, y1 = points[p1]\n",
    "            x_1, y_1 = points[p2]\n",
    "            x2, y2 = points[p3]\n",
    "            x_2, y_2 = points[p4]\n",
    "\n",
    "            line1 = vector(x1, y1, x2, y2)\n",
    "            line2 = vector(x1, y1, x_2, y_2)       \n",
    "\n",
    "            if line1[0]*line2[0] + line2[1]*line1[1]!=0:\n",
    "                return float('inf')\n",
    "            return dist(x1, y1, x2, y2) * dist(x1, y1, x_2, y_2)  \n",
    "        \n",
    "        centers = defaultdict(list)\n",
    "        for i in range(n-1):\n",
    "            x1, y1 = points[i]\n",
    "            for j in range(i+1, n):\n",
    "                x2, y2 = points[j]\n",
    "                centers[((x1 + x2)/2, (y1 + y2)/2)].append((i,j))\n",
    "        # print(centers)\n",
    "        ans = float('inf')\n",
    "        for k in centers:\n",
    "            n = len(centers[k])\n",
    "            for i in range(n-1):\n",
    "                l1, r1 = centers[k][i]\n",
    "                for j in range(i+1, n):\n",
    "                    if l1 in centers[k][j] or r1 in centers[k][j]:continue\n",
    "                    l2, r2 = centers[k][j]\n",
    "                    ans = min(ans, area(l1, r1, l2, r2))\n",
    "        \n",
    "        return ans if ans < float('inf') else 0   \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaFreeRect(self, points: List[List[int]]) -> float:\n",
    "        n=len(points)\n",
    "        def dist(x1, y1, x2, y2):\n",
    "            return ((x1-x2)**2 + (y1-y2)**2)**.5\n",
    "        \n",
    "        def vector(x1, y1, x2, y2):\n",
    "            return (x1-x2, y1-y2)\n",
    "\n",
    "        def area(p1, p2, p3, p4):\n",
    "            x1, y1 = points[p1]\n",
    "            x_1, y_1 = points[p2]\n",
    "            x2, y2 = points[p3]\n",
    "            x_2, y_2 = points[p4]\n",
    "\n",
    "            line1 = vector(x1, y1, x2, y2)\n",
    "            line2 = vector(x1, y1, x_2, y_2)       \n",
    "\n",
    "            if line1[0]*line2[0] + line2[1]*line1[1]!=0:\n",
    "                return float('inf')\n",
    "            return dist(x1, y1, x2, y2) * dist(x1, y1, x_2, y_2)  \n",
    "        \n",
    "        centers = defaultdict(list)\n",
    "        for i in range(n-1):\n",
    "            x1, y1 = points[i]\n",
    "            for j in range(i+1, n):\n",
    "                x2, y2 = points[j]\n",
    "                centers[((x1 + x2)/2, (y1 + y2)/2)].append((i,j))\n",
    "\n",
    "        ans = float('inf')\n",
    "        for k in centers:\n",
    "            n = len(centers[k])\n",
    "            for i in range(n-1):\n",
    "                l1, r1 = centers[k][i]\n",
    "                for j in range(i+1, n):\n",
    "                    if l1 in centers[k][j] or r1 in centers[k][j]: continue # 共点情况\n",
    "                    l2, r2 = centers[k][j]\n",
    "                    ans = min(ans, area(l1, r1, l2, r2))\n",
    "        \n",
    "        return ans if ans < float('inf') else 0   \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaFreeRect(self, points: List[List[int]]) -> float:\n",
    "        n=len(points)\n",
    "        def dist(x1, y1, x2, y2):\n",
    "            return ((x1-x2)**2 + (y1-y2)**2)**.5\n",
    "        \n",
    "        def vector(x1, y1, x2, y2):\n",
    "            return (x1-x2, y1-y2)\n",
    "\n",
    "        def area(p1, p2, p3, p4):\n",
    "            x1, y1 = points[p1]\n",
    "            x_1, y_1 = points[p2]\n",
    "            x2, y2 = points[p3]\n",
    "            x_2, y_2 = points[p4]\n",
    "\n",
    "            line1 = vector(x1, y1, x2, y2)\n",
    "            line2 = vector(x1, y1, x_2, y_2)       \n",
    "\n",
    "            if line1[0]*line2[0] + line2[1]*line1[1]!=0:\n",
    "                return float('inf')\n",
    "            return dist(x1, y1, x2, y2) * dist(x1, y1, x_2, y_2)  \n",
    "        \n",
    "        centers = defaultdict(list)\n",
    "        for i in range(n-1):\n",
    "            x1, y1 = points[i]\n",
    "            for j in range(i+1, n):\n",
    "                x2, y2 = points[j]\n",
    "                centers[((x1 + x2)/2, (y1 + y2)/2)].append((i,j))\n",
    "        print(centers)\n",
    "        ans = float('inf')\n",
    "        for k in centers:\n",
    "            n = len(centers[k])\n",
    "            for i in range(n-1):\n",
    "                l1, r1 = centers[k][i]\n",
    "                for j in range(i+1, n):\n",
    "                    # if l1 in centers[k][j] or r1 in centers[k][j]: continue \n",
    "                    l2, r2 = centers[k][j]\n",
    "                    ans = min(ans, area(l1, r1, l2, r2))\n",
    "        \n",
    "        return ans if ans < float('inf') else 0   \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaFreeRect(self, points: List[List[int]]) -> float:\n",
    "        n=len(points)\n",
    "        def dist(x1, y1, x2, y2):\n",
    "            return ((x1-x2)**2 + (y1-y2)**2)**.5\n",
    "        \n",
    "        def vector(x1, y1, x2, y2):\n",
    "            return (x1-x2, y1-y2)\n",
    "\n",
    "        def area(p1, p2, p3, p4):\n",
    "            x1, y1 = points[p1]\n",
    "            x_1, y_1 = points[p2]\n",
    "            x2, y2 = points[p3]\n",
    "            x_2, y_2 = points[p4]\n",
    "\n",
    "            line1 = vector(x1, y1, x2, y2)\n",
    "            line2 = vector(x1, y1, x_2, y_2)       \n",
    "\n",
    "            if line1[0]*line2[0] + line2[1]*line1[1]!=0:\n",
    "                return float('inf')\n",
    "            return dist(x1, y1, x2, y2) * dist(x1, y1, x_2, y_2)  \n",
    "        \n",
    "        centers = defaultdict(list)\n",
    "        for i in range(n-1):\n",
    "            x1, y1 = points[i]\n",
    "            for j in range(i+1, n):\n",
    "                x2, y2 = points[j]\n",
    "                centers[((x1 + x2)/2, (y1 + y2)/2)].append((i,j))\n",
    "        print(centers)\n",
    "        ans = float('inf')\n",
    "        for k in centers:\n",
    "            n = len(centers[k])\n",
    "            for i in range(n-1):\n",
    "                l1, r1 = centers[k][i]\n",
    "                for j in range(i+1, n):\n",
    "                    l2, r2 = centers[k][j]\n",
    "                    ans = min(ans, area(l1, r1, l2, r2))\n",
    "        \n",
    "        return ans if ans < float('inf') else 0   \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaFreeRect(self, points: List[List[int]]) -> float:\n",
    "        kmap = {}\n",
    "        pmap = {}\n",
    "        wmap = {}\n",
    "        n = len(points)\n",
    "        for i in range(n):\n",
    "            x1, y1 = points[i]\n",
    "            for j in range(i):\n",
    "                x2, y2 = points[j]\n",
    "                if(x1 == x2):\n",
    "                    if('inf' not in kmap):\n",
    "                        kmap['inf'] = []\n",
    "                    kmap['inf'].append((j,i))\n",
    "                    pmap[(j,i)] = 'inf'\n",
    "                    pmap[(i,j)] = 'inf'\n",
    "                    wmap[(j,i)] = sqrt((x1-x2)**2+(y1-y2)**2)\n",
    "                    wmap[(i,j)] = sqrt((x1-x2)**2+(y1-y2)**2)\n",
    "                else:\n",
    "                    k = (y1-y2)/(x1-x2)\n",
    "                    if(k not in kmap):\n",
    "                        kmap[k] = []\n",
    "                    kmap[k].append((j,i))\n",
    "                    pmap[(j,i)] = k\n",
    "                    pmap[(i,j)] = k\n",
    "                    wmap[(j,i)] = sqrt((x1-x2)**2+(y1-y2)**2)\n",
    "                    wmap[(i,j)] = sqrt((x1-x2)**2+(y1-y2)**2)\n",
    "        result = float('inf')\n",
    "        for k, ps in kmap.items():\n",
    "            for i in range(len(ps)):\n",
    "                p1, p2 = ps[i]\n",
    "                for j in range(i):\n",
    "                    p3, p4 = ps[j]\n",
    "                    if(k == 'inf'):\n",
    "                        if((p1,p3) in pmap and (p2,p4) in pmap and pmap[(p1,p3)] == 0 and pmap[(p2,p4)] == 0):\n",
    "                            result  = min(result, wmap[(p1,p2)]*wmap[(p1,p3)])\n",
    "                        if((p1,p4) in pmap and (p2,p3) in pmap and pmap[(p1,p4)] == 0 and pmap[(p2,p3)] == 0):\n",
    "                            result  = min(result, wmap[(p1,p2)]*wmap[(p1,p4)])\n",
    "                    else:\n",
    "                        if(k == 0 and (p1,p3) in pmap and (p2,p4) in pmap and pmap[(p1,p3)] == 'inf' and pmap[(p2,p4)] == 'inf'):\n",
    "                            result  = min(result, wmap[(p1,p2)]*wmap[(p1,p3)])\n",
    "                        elif((p1,p3) in pmap and (p2,p4) in pmap and pmap[(p1,p3)] != 'inf' and pmap[(p2,p4)] != 'inf' and abs(pmap[(p1,p3)]*k+1) < 0.0001 and abs(pmap[(p2,p4)]*k+1) < 0.0001):\n",
    "                            result  = min(result, wmap[(p1,p2)]*wmap[(p1,p3)])\n",
    "                        elif(k == 0 and (p1,p4) in pmap and (p2,p3) in pmap and pmap[(p1,p4)] == 'inf' and pmap[(p2,p3)] == 'inf'):\n",
    "                            result  = min(result, wmap[(p1,p2)]*wmap[(p1,p4)])\n",
    "                        elif((p1,p4) in pmap and (p2,p3) in pmap and pmap[(p1,p4)]!='inf' and pmap[(p2,p3)]!='inf' and abs(pmap[(p1,p4)]*k+1) < 0.0001 and abs(pmap[(p2,p3)]*k+1) < 0.0001):\n",
    "                            result  = min(result, wmap[(p1,p2)]*wmap[(p1,p4)])\n",
    "                    \n",
    "        return result if result < float('inf') else 0.\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAreaFreeRect(self, points: List[List[int]]) -> float:\n",
    "        kmap = {}\n",
    "        pmap = {}\n",
    "        wmap = {}\n",
    "        n = len(points)\n",
    "        for i in range(n):\n",
    "            x1, y1 = points[i]\n",
    "            for j in range(i):\n",
    "                x2, y2 = points[j]\n",
    "                if(x1 == x2):\n",
    "                    if('inf' not in kmap):\n",
    "                        kmap['inf'] = []\n",
    "                    kmap['inf'].append((j,i))\n",
    "                    pmap[(j,i)] = 'inf'\n",
    "                    pmap[(i,j)] = 'inf'\n",
    "                    wmap[(j,i)] = sqrt((x1-x2)**2+(y1-y2)**2)\n",
    "                    wmap[(i,j)] = sqrt((x1-x2)**2+(y1-y2)**2)\n",
    "                else:\n",
    "                    k = (y1-y2)/(x1-x2)\n",
    "                    if(k not in kmap):\n",
    "                        kmap[k] = []\n",
    "                    kmap[k].append((j,i))\n",
    "                    pmap[(j,i)] = k\n",
    "                    pmap[(i,j)] = k\n",
    "                    wmap[(j,i)] = sqrt((x1-x2)**2+(y1-y2)**2)\n",
    "                    wmap[(i,j)] = sqrt((x1-x2)**2+(y1-y2)**2)\n",
    "        result = float('inf')\n",
    "        for k, ps in kmap.items():\n",
    "            for i in range(len(ps)):\n",
    "                p1, p2 = ps[i]\n",
    "                for j in range(i):\n",
    "                    p3, p4 = ps[j]\n",
    "                    if(k == 'inf'):\n",
    "                        if((p1,p3) in pmap and (p2,p4) in pmap and pmap[(p1,p3)] == 0 and pmap[(p2,p4)] == 0):\n",
    "                            result  = min(result, wmap[(p1,p2)]*wmap[(p1,p3)])\n",
    "                        if((p1,p4) in pmap and (p2,p3) in pmap and pmap[(p1,p4)] == 0 and pmap[(p2,p3)] == 0):\n",
    "                            result  = min(result, wmap[(p1,p2)]*wmap[(p1,p4)])\n",
    "                    else:\n",
    "                        if(k == 0 and (p1,p3) in pmap and (p2,p4) in pmap and pmap[(p1,p3)] == 'inf' and pmap[(p2,p4)] == 'inf'):\n",
    "                            result  = min(result, wmap[(p1,p2)]*wmap[(p1,p3)])\n",
    "                        elif((p1,p3) in pmap and (p2,p4) in pmap and pmap[(p1,p3)] != 'inf' and pmap[(p2,p4)] != 'inf' and abs(pmap[(p1,p3)]*k+1) < 0.0001 and abs(pmap[(p2,p4)]*k+1) < 0.0001):\n",
    "                            result  = min(result, wmap[(p1,p2)]*wmap[(p1,p3)])\n",
    "                        elif(k == 0 and (p1,p4) in pmap and (p2,p3) in pmap and pmap[(p1,p4)] == 'inf' and pmap[(p2,p3)] == 'inf'):\n",
    "                            result  = min(result, wmap[(p1,p2)]*wmap[(p1,p4)])\n",
    "                        elif((p1,p4) in pmap and (p2,p3) in pmap and pmap[(p1,p4)]!='inf' and pmap[(p2,p3)]!='inf' and abs(pmap[(p1,p4)]*k+1) < 0.0001 and abs(pmap[(p2,p3)]*k+1) < 0.0001):\n",
    "                            result  = min(result, wmap[(p1,p2)]*wmap[(p1,p4)])\n",
    "                    \n",
    "        return result if result < float('inf') else 0.\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
